home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 12 / Cream of the Crop 12 (Part II) / Cream of the Crop 12 (Part II).iso / OS2 / DIKUMUD.ZIP / BSD.C < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-28  |  12.1 KB  |  491 lines
  1. /*
  2.  * Copyright (c) 1988 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34.  
  35.  
  36.  
  37. #include <string.h>
  38. /*#include <stdlib.h>*/
  39. /*#include <bsd/types.h>*/
  40. /*#include <sys/cdefs.h>*/
  41. #include <sys/types.h>
  42. #include <unistd.h>
  43.  
  44. #define    NULL 0
  45.  
  46. #ifdef KLUDGE_MEM
  47. static void morecore();
  48. static int findbucket();
  49. #endif
  50.  
  51. #ifdef KLUDGE_STRING
  52. char *
  53. strdup(str)
  54.     const char *str;
  55. {
  56.     int len;
  57.     char *copy;
  58.  
  59.     len = strlen(str) + 1;
  60.     if (!(copy = (char *)malloc((u_int)len)))
  61.         return((char *)NULL);
  62.     bcopy(str, copy, len);
  63.     return(copy);
  64. }
  65.  
  66.  
  67.  
  68.  
  69.  
  70. /*
  71.  * Find the first occurrence of find in s.
  72.  */
  73. char *
  74. strstr(s, find)
  75.     register const char *s, *find;
  76. {
  77.     register char c, sc;
  78.     register size_t len;
  79.  
  80.     if ((c = *find++) != 0) {
  81.         len = strlen(find);
  82.         do {
  83.             do {
  84.                 if ((sc = *s++) == 0)
  85.                     return (NULL);
  86.             } while (sc != c);
  87.         } while (strncmp(s, find, len) != 0);
  88.         s--;
  89.     }
  90.     return ((char *)s);
  91. }
  92. #endif
  93.  
  94.  
  95. /*
  96.  * malloc.c (Caltech) 2/21/82
  97.  * Chris Kingsley, kingsley@cit-20.
  98.  *
  99.  * This is a very fast storage allocator.  It allocates blocks of a small 
  100.  * number of different sizes, and keeps free lists of each size.  Blocks that
  101.  * don't exactly fit are passed up to the next larger size.  In this 
  102.  * implementation, the available sizes are 2^n-4 (or 2^n-10) bytes long.
  103.  * This is designed for use in a virtual memory environment.
  104.  */
  105.  
  106. /*
  107.  * The overhead on a block is at least 4 bytes.  When free, this space
  108.  * contains a pointer to the next free block, and the bottom two bits must
  109.  * be zero.  When in use, the first byte is set to MAGIC, and the second
  110.  * byte is the size index.  The remaining bytes are for alignment.
  111.  * If range checking is enabled then a second word holds the size of the
  112.  * requested block, less 1, rounded up to a multiple of sizeof(RMAGIC).
  113.  * The order of elements is critical: ov_magic must overlay the low order
  114.  * bits of ov_next, and ov_magic can not be a valid ov_next bit pattern.
  115.  */
  116. #ifdef KLUDGE_MEM
  117. union    overhead {
  118.     union    overhead *ov_next;    /* when free */
  119.     struct {
  120.         u_char    ovu_magic;    /* magic number */
  121.         u_char    ovu_index;    /* bucket # */
  122. #ifdef RCHECK
  123.         u_short    ovu_rmagic;    /* range magic number */
  124.         u_int    ovu_size;    /* actual block size */
  125. #endif
  126.     } ovu;
  127. #define    ov_magic    ovu.ovu_magic
  128. #define    ov_index    ovu.ovu_index
  129. #define    ov_rmagic    ovu.ovu_rmagic
  130. #define    ov_size        ovu.ovu_size
  131. };
  132.  
  133. #define    MAGIC        0xef        /* magic # on accounting info */
  134. #define RMAGIC        0x5555        /* magic # on range info */
  135.  
  136. #ifdef RCHECK
  137. #define    RSLOP        sizeof (u_short)
  138. #else
  139. #define    RSLOP        0
  140. #endif
  141.  
  142. /*
  143.  * nextf[i] is the pointer to the next free block of size 2^(i+3).  The
  144.  * smallest allocatable block is 8 bytes.  The overhead information
  145.  * precedes the data area returned to the user.
  146.  */
  147. #define    NBUCKETS 30
  148. static    union overhead *nextf[NBUCKETS];
  149. extern    char *sbrk();
  150.  
  151. static    int pagesz;            /* page size */
  152. static    int pagebucket;            /* page size bucket */
  153.  
  154. #ifdef MSTATS
  155. /*
  156.  * nmalloc[i] is the difference between the number of mallocs and frees
  157.  * for a given block size.
  158.  */
  159. static    u_int nmalloc[NBUCKETS];
  160. #include <stdio.h>
  161. #endif
  162.  
  163. #if defined(DEBUG) || defined(RCHECK)
  164. #define    ASSERT(p)   if (!(p)) botch("p")
  165. #include <stdio.h>
  166. static
  167. botch(s)
  168.     char *s;
  169. {
  170.     fprintf(stderr, "\r\nassertion botched: %s\r\n", s);
  171.      (void) fflush(stderr);        /* just in case user buffered it */
  172.     abort();
  173. }
  174. #else
  175. #define    ASSERT(p)
  176. #endif
  177.  
  178. void *
  179. malloc(nbytes)
  180.     size_t nbytes;
  181. {
  182.       register union overhead *op;
  183.       register int bucket, n;
  184.     register unsigned amt;
  185.  
  186.     /*
  187.      * First time malloc is called, setup page size and
  188.      * align break pointer so all data will be page aligned.
  189.      */
  190.     if (pagesz == 0) {
  191.         pagesz = n = getpagesize();
  192.         op = (union overhead *)sbrk(0);
  193.           n = n - sizeof (*op) - ((int)op & (n - 1));
  194.         if (n < 0)
  195.             n += pagesz;
  196.           if (n) {
  197.               if (sbrk(n) == (char *)-1)
  198.                 return (NULL);
  199.         }
  200.         bucket = 0;
  201.         amt = 8;
  202.         while (pagesz > amt) {
  203.             amt <<= 1;
  204.             bucket++;
  205.         }
  206.         pagebucket = bucket;
  207.     }
  208.     /*
  209.      * Convert amount of memory requested into closest block size
  210.      * stored in hash buckets which satisfies request.
  211.      * Account for space used per block for accounting.
  212.      */
  213.     if (nbytes <= (n = pagesz - sizeof (*op) - RSLOP)) {
  214. #ifndef RCHECK
  215.         amt = 8;    /* size of first bucket */
  216.         bucket = 0;
  217. #else
  218.         amt = 16;    /* size of first bucket */
  219.         bucket = 1;
  220. #endif
  221.         n = -(sizeof (*op) + RSLOP);
  222.     } else {
  223.         amt = pagesz;
  224.         bucket = pagebucket;
  225.     }
  226.     while (nbytes > amt + n) {
  227.         amt <<= 1;
  228.         if (amt == 0)
  229.             return (NULL);
  230.         bucket++;
  231.     }
  232.     /*
  233.      * If nothing in hash bucket right now,
  234.      * request more memory from the system.
  235.      */
  236.       if ((op = nextf[bucket]) == NULL) {
  237.           morecore(bucket);
  238.           if ((op = nextf[bucket]) == NULL)
  239.               return (NULL);
  240.     }
  241.     /* remove from linked list */
  242.       nextf[bucket] = op->ov_next;
  243.     op->ov_magic = MAGIC;
  244.     op->ov_index = bucket;
  245. #ifdef MSTATS
  246.       nmalloc[bucket]++;
  247. #endif
  248. #ifdef RCHECK
  249.     /*
  250.      * Record allocated size of block and
  251.      * bound space with magic numbers.
  252.      */
  253.     op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  254.     op->ov_rmagic = RMAGIC;
  255.       *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  256. #endif
  257.       return ((char *)(op + 1));
  258. }
  259.  
  260. /*
  261.  * Allocate more memory to the indicated bucket.
  262.  */
  263. static void
  264. morecore(bucket)
  265.     int bucket;
  266. {
  267.       register union overhead *op;
  268.     register int sz;        /* size of desired block */
  269.       int amt;            /* amount to allocate */
  270.       int nblks;            /* how many blocks we get */
  271.  
  272.     /*
  273.      * sbrk_size <= 0 only for big, FLUFFY, requests (about
  274.      * 2^30 bytes on a VAX, I think) or for a negative arg.
  275.      */
  276.     sz = 1 << (bucket + 3);
  277. #ifdef DEBUG
  278.     ASSERT(sz > 0);
  279. #else
  280.     if (sz <= 0)
  281.         return;
  282. #endif
  283.     if (sz < pagesz) {
  284.         amt = pagesz;
  285.           nblks = amt / sz;
  286.     } else {
  287.         amt = sz + pagesz;
  288.         nblks = 1;
  289.     }
  290.     op = (union overhead *)sbrk(amt);
  291.     /* no more room! */
  292.       if ((int)op == -1)
  293.           return;
  294.     /*
  295.      * Add new memory allocated to that on
  296.      * free list for this hash bucket.
  297.      */
  298.       nextf[bucket] = op;
  299.       while (--nblks > 0) {
  300.         op->ov_next = (union overhead *)((caddr_t)op + sz);
  301.         op = (union overhead *)((caddr_t)op + sz);
  302.       }
  303. }
  304.  
  305. void
  306. free(cp)
  307.     void *cp;
  308. {   
  309.       register int size;
  310.     register union overhead *op;
  311.  
  312.       if (cp == NULL)
  313.           return;
  314.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  315. #ifdef DEBUG
  316.       ASSERT(op->ov_magic == MAGIC);        /* make sure it was in use */
  317. #else
  318.     if (op->ov_magic != MAGIC)
  319.         return;                /* sanity */
  320. #endif
  321. #ifdef RCHECK
  322.       ASSERT(op->ov_rmagic == RMAGIC);
  323.     ASSERT(*(u_short *)((caddr_t)(op + 1) + op->ov_size) == RMAGIC);
  324. #endif
  325.       size = op->ov_index;
  326.       ASSERT(size < NBUCKETS);
  327.     op->ov_next = nextf[size];    /* also clobbers ov_magic */
  328.       nextf[size] = op;
  329. #ifdef MSTATS
  330.       nmalloc[size]--;
  331. #endif
  332. }
  333.  
  334. /*
  335.  * When a program attempts "storage compaction" as mentioned in the
  336.  * old malloc man page, it realloc's an already freed block.  Usually
  337.  * this is the last block it freed; occasionally it might be farther
  338.  * back.  We have to search all the free lists for the block in order
  339.  * to determine its bucket: 1st we make one pass thru the lists
  340.  * checking only the first block in each; if that fails we search
  341.  * ``realloc_srchlen'' blocks in each list for a match (the variable
  342.  * is extern so the caller can modify it).  If that fails we just copy
  343.  * however many bytes was given to realloc() and hope it's not huge.
  344.  */
  345. int realloc_srchlen = 4;    /* 4 should be plenty, -1 =>'s whole list */
  346.  
  347. void *
  348. realloc(cp, nbytes)
  349.     void *cp; 
  350.     size_t nbytes;
  351. {   
  352.       register u_int onb;
  353.     register int i;
  354.     union overhead *op;
  355.       char *res;
  356.     int was_alloced = 0;
  357.  
  358.       if (cp == NULL)
  359.           return (malloc(nbytes));
  360.     op = (union overhead *)((caddr_t)cp - sizeof (union overhead));
  361.     if (op->ov_magic == MAGIC) {
  362.         was_alloced++;
  363.         i = op->ov_index;
  364.     } else {
  365.         /*
  366.          * Already free, doing "compaction".
  367.          *
  368.          * Search for the old block of memory on the
  369.          * free list.  First, check the most common
  370.          * case (last element free'd), then (this failing)
  371.          * the last ``realloc_srchlen'' items free'd.
  372.          * If all lookups fail, then assume the size of
  373.          * the memory block being realloc'd is the
  374.          * largest possible (so that all "nbytes" of new
  375.          * memory are copied into).  Note that this could cause
  376.          * a memory fault if the old area was tiny, and the moon
  377.          * is gibbous.  However, that is very unlikely.
  378.          */
  379.         if ((i = findbucket(op, 1)) < 0 &&
  380.             (i = findbucket(op, realloc_srchlen)) < 0)
  381.             i = NBUCKETS;
  382.     }
  383.     onb = 1 << (i + 3);
  384.     if (onb < pagesz)
  385.         onb -= sizeof (*op) + RSLOP;
  386.     else
  387.         onb += pagesz - sizeof (*op) - RSLOP;
  388.     /* avoid the copy if same size block */
  389.     if (was_alloced) {
  390.         if (i) {
  391.             i = 1 << (i + 2);
  392.             if (i < pagesz)
  393.                 i -= sizeof (*op) + RSLOP;
  394.             else
  395.                 i += pagesz - sizeof (*op) - RSLOP;
  396.         }
  397.         if (nbytes <= onb && nbytes > i) {
  398. #ifdef RCHECK
  399.             op->ov_size = (nbytes + RSLOP - 1) & ~(RSLOP - 1);
  400.             *(u_short *)((caddr_t)(op + 1) + op->ov_size) = RMAGIC;
  401. #endif
  402.             return(cp);
  403.         } else
  404.             free(cp);
  405.     }
  406.       if ((res = malloc(nbytes)) == NULL)
  407.           return (NULL);
  408.       if (cp != res)        /* common optimization if "compacting" */
  409.         bcopy(cp, res, (nbytes < onb) ? nbytes : onb);
  410.       return (res);
  411. }
  412.  
  413. /*
  414.  * Search ``srchlen'' elements of each free list for a block whose
  415.  * header starts at ``freep''.  If srchlen is -1 search the whole list.
  416.  * Return bucket number, or -1 if not found.
  417.  */
  418. static
  419. findbucket(freep, srchlen)
  420.     union overhead *freep;
  421.     int srchlen;
  422. {
  423.     register union overhead *p;
  424.     register int i, j;
  425.  
  426.     for (i = 0; i < NBUCKETS; i++) {
  427.         j = 0;
  428.         for (p = nextf[i]; p && j != srchlen; p = p->ov_next) {
  429.             if (p == freep)
  430.                 return (i);
  431.             j++;
  432.         }
  433.     }
  434.     return (-1);
  435. }
  436.  
  437. #ifdef MSTATS
  438. /*
  439.  * mstats - print out statistics about malloc
  440.  * 
  441.  * Prints two lines of numbers, one showing the length of the free list
  442.  * for each size category, the second showing the number of mallocs -
  443.  * frees for each size category.
  444.  */
  445. mstats(s)
  446.     char *s;
  447. {
  448.       register int i, j;
  449.       register union overhead *p;
  450.       int totfree = 0,
  451.       totused = 0;
  452.  
  453.       fprintf(stderr, "Memory allocation statistics %s\nfree:\t", s);
  454.       for (i = 0; i < NBUCKETS; i++) {
  455.           for (j = 0, p = nextf[i]; p; p = p->ov_next, j++)
  456.               ;
  457.           fprintf(stderr, " %d", j);
  458.           totfree += j * (1 << (i + 3));
  459.       }
  460.       fprintf(stderr, "\nused:\t");
  461.       for (i = 0; i < NBUCKETS; i++) {
  462.           fprintf(stderr, " %d", nmalloc[i]);
  463.           totused += nmalloc[i] * (1 << (i + 3));
  464.       }
  465.       fprintf(stderr, "\n\tTotal in use: %d, total free: %d\n",
  466.         totused, totfree);
  467. }
  468. #endif
  469.  
  470.  
  471. void *
  472. calloc(num, size)
  473.     size_t num;
  474.     register size_t size;
  475. {
  476.     register void *p;
  477.  
  478.     size *= num;
  479.     if (p = (void *)malloc(size))
  480.         bzero(p, size);
  481.     return(p);
  482. }
  483.  
  484. void
  485. cfree(p)
  486.     void *p;
  487. {
  488.     (void)free(p);
  489. }
  490. #endif
  491.